package com.atguigui.leetcode;

/**
 * 668.乘法表中第k小的数
 * Project: leetcode
 * Package: com.atguigui.leetcode
 * Version: 1.0
 * <p>
 * Created by WJX on 2022/5/18 9:31
 */
public class P668KthSmallestNumberInMultiplicationTable {
    public static void main(String[] args) {
        Solution solution = new P668KthSmallestNumberInMultiplicationTable().new Solution();
        // TO TEST
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int findKthNumber(int m, int n, int k) {
            int left = 1, right = m * n;
            while (left < right) {
                // 二分查找
                // 切分一半后+left
                int x = left + (right - left) / 2;


                int count = x / n * n;
                for (int i = x / n + 1; i <= m; ++i) {
                    count += x / i;
                }
                if (count >= k) {
                    // 缩小右边
                    right = x;
                } else {
                    // 左边+1
                    left = x + 1;
                }
            }
            return left;
        }
    }
}
